#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;

const int N = 1e6 + 10, INF = 0x3f3f3f3f;

int prim[N], R;
int p[N], cnt[N];//p表示i最小质因子的个数，cnt表示约数的个数
bool st[N];

void get_primes(int n)
{
    cnt[1] = 1;
    for (int i = 2;i <= n;i++) {
        if (st[i] == 0) {
            prim[++R] = i;
            p[i] = 1, cnt[i] = 2;//质数的最小质因子为本身，约数为2
        }
        for (int j = 1;prim[j] * i <= n;j++) {
            st[i * prim[j]] = 1;
            if (i % prim[j] == 0) {
                // i % prim[j] == 0说明i中至少有一个质因子prim[j]
                p[i * prim[j]] = p[i] + 1;//i * prim[j]的最小质因子的个数为i的最小质因子个数+1
                //可以知道i的约数个数=(a1 + 1)(a2 + 1)(a3 + 1)...(an + 1)
                //i * prim[j]的约数个数=(a1 + 1 + 1)(a2 + 1)(a3 + 1)...(an + 1)
                //去掉(a1 + 1)在乘以(a1 + 2)即为i * prim[j]的约数个数
                cnt[i * prim[j]] = cnt[i] / (p[i] + 1) * (p[i] + 2);
                break;
            } else {
                //prim[j]必然是i * prim[j] 的最小质因子,i * prim[j]的最小质因子个数为1
                p[i * prim[j]] = 1;
                //对于i来说没有约数prim[j],i *prim[j]有约数prim[j],所以i的约数个数乘以prim[j]的约数个数
                cnt[i * prim[j]] = cnt[i] * 2;
            }
        }
    }
}
